package main.链表;

import common.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author tmh
 * @date 2024/7/20 13:58
 * @description
 */
public class T142环形链表II {
    /**
     * 用的是map的思路来找环
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        Map<ListNode, Integer> map = new HashMap<>();
        int index = 0;
        while (head != null) {
            if (map.containsKey(head)) {
                return head;
            } else {
                map.put(head, index++);
            }
            head = head.next;
        }
        return head;
    }

    /**
     * 用快慢指针的思路来解决
     *
     * @param head
     * @return
     */
    public ListNode detectCycle1(ListNode head) {
        //定义两个指针：快 慢
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            //慢指针移动一步
            slow = slow.next;
            //快指针移动两步
            fast = fast.next.next;
            //如果快慢指针相遇
            if (slow == fast) {
                //定义两个指针来指向相遇节点和头节点
                ListNode index1 = fast;
                ListNode index2 = head;
                //当index1和index2相同的时候，他们所指向的节点就是入环的第一个节点
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

}
